package com.code.test.first.dp;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.md
 * 斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你n ，请计算 F(n) 。
 * <p>
 * 示例 1：
 * <p>
 * 输入：2
 * 输出：1
 * 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
 * 示例 2：
 * <p>
 * 输入：3
 * 输出：2
 * 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
 * 示例 3：
 * <p>
 * 输入：4
 * 输出：3
 * 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
 * 提示：
 * <p>
 * 0 <= n <= 30
 */
public class Code509 {

    public static void main(String[] args) {
        int ret = fib3(10);
        System.out.println(ret);
    }

    public static int fib(int n) {
        if (n < 2) {
            return n;
        }
        int sum = 0;
        int first = 0;
        int second = 1;
        for (int i = 1; i < n; i++) {
            sum = first + second;
            first = second;
            second = sum;

        }
        return sum;
    }

    /**
     * n代表第几个数，意思是要计算斐波那契数列的第n个数是多少
     * @param n
     * @return
     */
    public static int fib2(int n) {
        //为什么是n+1？
        int[] dp = new int[n];
        if (n < 2) {
            return n;
        }
        //前2个都是1
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i < n; i++) {
            //每一个都是前2个的相加
            /**
             *  1,1,2,3,5,8,13 这是7个数
             *  数组大小是n
             *
             */
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n-1];
    }

    public static int fib3(int n) {
        //为什么是n+1？
        int[] dp = new int[n+1];
        if (n < 2) {
            return n;
        }
        //前2个都是1
        dp[0] = 0;
        dp[1] = 1;

        //数组多一个数，这里要计算到最后一个数，因为dp[0]=0,正常应该是1，这里初始化为0，所以要到n，以及dp数组大小为n+1
        for (int i = 2; i <= n; i++) {
            //每一个都是前2个的相加
            /**
             *  1,1,2,3,5,8,13 这是7个数
             *  数组大小是n
             *
             */
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
